package cn.lishiyuan.algorithm.strings;

import java.util.*;
import java.util.function.Function;

/**
 * AC自动机多模式匹配
 */
public class ACMatcher  {
    // 分词
    private final Function<String,List<String>> split;
    // 合并词
    private final Function<List<String>,String> merge;

    private final Node root;

    private static class Node{
        String word;

        // 子节点
        Map<String, Node> children;

        // 是否是最后一个字母或者单词
        boolean isEndWord = false;

        int length = 0;

        Node fail;

        Node(String word){
            this.word = word;
            this.children = new HashMap<>();
            fail = null;
        }
    }

    public ACMatcher(Function<String,List<String>> split, Function<List<String>,String> merge){
        this.split = split;
        this.merge = merge;
        this.root = new Node(null);
    }

    public void insert(String words){
        if (words == null || words.trim().isEmpty()){
            return;
        }

        // 分词，构建树节点
        List<String> wordsList = split.apply(words);
        // 匹配字典数据
        Node parent = root;

        for (int i = 0; i < wordsList.size(); i++) {

            String word = wordsList.get(i);
            if (parent.children.containsKey(word)){
                // 存在相同节点则继续向后查找
                parent = parent.children.get(word);
            }else {
                Node node = new Node(word);
                node.isEndWord = (i == (wordsList.size() - 1));
                if(node.isEndWord){
                    // 分词后的长度
                    node.length = wordsList.size();
                }
                parent.children.put(word,node);
                parent = node;
            }
        }

    }

    // 全部敏感词插入完成后
    // 手动构建fail指针
    public void buildFailure() {
        // 通过广度优先遍历构建fail指针
        Queue<Node> queue = new LinkedList<>();
        root.fail = null;
        for (Node child : root.children.values()) {
            // root的子节点的fail指针是root
            child.fail = root;
            queue.add(child);
        }
        while (!queue.isEmpty()) {
            Node current = queue.poll();
            for (Map.Entry<String, Node> entry : current.children.entrySet()) {
                Node child = entry.getValue();
                // 父节点的失败指针
                Node fail = current.fail;
                while (fail != null && !fail.children.containsKey(entry.getKey())) {
                    // 失败指针的失败指针
                    fail = fail.fail;
                }
                // 如果没找到就指向root
                child.fail = (fail != null) ? fail.children.get(entry.getKey()) : root;
                queue.add(child);
            }
        }
    }

    public List<String> find(String text){
        if (text == null || text.trim().isEmpty()){
            return Collections.emptyList();
        }

        // 如果不最后一个词（也就是中途break了），则返回空列表
        List<String> result = new ArrayList<>();

        // 分词，构建树节点
        List<String> wordsList = split.apply(text);
        // 匹配字典数据
        Node parent = root;

        for (int startIndex = 0; startIndex < wordsList.size(); startIndex++) {

            String key = wordsList.get(startIndex);
            // index 只有一个方向
            // 字典如果没有查找到就从下个字重新开始查找
            if (parent.children.containsKey(key)) {
                parent = parent.children.get(key);
                // 查找下一个字符
                extractWord(parent, wordsList,result, startIndex);
            }else {
                Node fail = parent.fail;
                // 如果不为null且fail子节点不包含下个词，则还需要再从缩小查找范围
                while (fail!=null && !fail.children.containsKey(key)){
                    fail = fail.fail;
                }
                if (fail == null){
                    // 不是敏感词
                    parent = root;
                }else {
                    // 查到了，继续查找
                    parent = fail.children.get(key);
                    extractWord(parent, wordsList,result, startIndex);
                }

            }

        }

        return result;
    }

    private void extractWord(Node parent, List<String> wordsList,List<String> result, int startIndex) {
        Node current = parent;
        while (current != root) {
            if (current.isEndWord) {
                // 记录单词
                List<String> list = wordsList.subList(startIndex - current.length + 1, startIndex + 1);
                String word = merge.apply(list);
                result.add(word);
            }
            current = current.fail;
        }
    }

    public boolean match(String test){
        List<String> words = find(test);
        return !words.isEmpty();
    }

}
